% !Mode:: "TeX:UTF-8"
\chapter{Исследование методов построения тестовых программ}

\section{Системное тестирование микропроцессоров}

Прежде, чем описывать методы построения тестовых программ, следует дать понятие о самом системном тестировании более четко.
\begin{figure}[h] \center
  \includegraphics[width=0.7\textwidth]{1.review/test-system}\\
  \caption{Архитектура тестовой системы}\label{fig:test_system}
\end{figure}

На рисунке~\ref{fig:test_system} приведена архитектура тестовой системы, общеупотребительная как для аппаратного, так и для программного обеспечения~\cite{IvanPreprint} (везде, где говорится об аппаратном обеспечении, подразумеваются их программные модели на языках Verilog/VHDL). В рамках системного тестирования (как и любого тестирования) работа микропроцессора проверяется в ситуациях из выделенного конечного набора (в \emph{тестовых ситуациях}). Генератор тестовой последовательности строит \emph{тестовые воздействия} (в случае системного тестирования это программы на машинном языке --- тестовые программы) и передает их на тестируемый компонент (каждая сгенерированная программа запускается на программной модели микропроцессора). В результате с тестируемого компонента считывается \emph{реакция} (значения регистров в разное время, содержимое кэш-памяти, таблицы страниц, возникшие исключительные ситуации и т.п.). Реакция и те же тестовые воздействия передаются \emph{тестовому оракулу}, задачей которого является оценка соответствия полученной реакции тестовому воздействию (что из себя представляет тестовый оракул в случае системного тестирования будет сказано чуть позже). В результате своей работы тестовый оракул составляет \emph{тестовый отчет}, в котором отражены подававшиеся тестовые воздействия (точнее, из каких классов подавались тестовые воздействия, какие тестовые ситуации были задействованы), полученные реакции и вердикты оценки их соответствия.

Тестовый оракул (в случае системного тестирования) может быть построен следующими способами:
\begin{itemize}
  \item \emph{ко-симуляция}~\cite{HoPhD}: разрабатывается программная модель тестируемого микропроцессора, более простая, нежели тестируемая модель (такими программными моделями могут быть эмулятор микропроцессора, интерпретатор системы команд); обычно такие модели разрабатываются на языках высокого уровня, например, на Си или Си++; это делают люди, не занятые в разработке тестируемой модели для исключения возможности одинаковых ошибок в обеих моделях; тестовый оракул подает переданные ему тестовые воздействия на эту <<эталонную>> модель, получает ее реакции и сравнивает их с реакциями тестируемой модели;

  \item \emph{самопроверяющие тесты}~\cite{HoPhD}: реакция тестируемой модели на исполнение самопроверяющих тестов уже содержит в себе вердикт, поэтому тестовый оракул извлекает информацию для тестового отчета из реакции; самопроверяющими тестами могут быть тестовые программы, в которых (как следует из названия) после <<основной>> части тестового воздействия идут инструкции, анализирующие текущее состояние микропроцессора и выставляющие специальные флаги, пищущие специальные тексты на терминал и т.п. (например, что заданные регистры получили нужные значения);

  \item \emph{на основе формальных спецификаций}~\cite{KamkinThesis}: тестовый оракул использует технику пред- и пост-условий для определения соответствия переданных ему тестовых воздействий и реакций.
\end{itemize}

Методы автоматической генерации тестовых программ делят на псевдослучайные/комбинаторные и целенаправленные~\cite{HoPhD}. В случае псевдослучайной генерации инструкции для тестовой программы. Методы целенаправленного построения тестовых программ существенного опираются на выбранные тестовые ситуации (или классы тестовых ситуаций). Их целенаправленность заключается в том, что процедура построения тестовой программы работают с каждой конкретной тестовой ситуацией (см. рисунок~\ref{fig:directed_methods}). Систематический выбор (всех)(классов) тестовых ситуаций и целенаправленное построение на них тестовых программ --- это путь к более тщательному тестированию, нежели псевдослучайное построение тестовых программ. В последнем случае покрытие заданных тестовых ситуаций не гарантируется.

\begin{figure}[h] \center
  \includegraphics[width=0.7\textwidth]{1.review/methods2}\\
  \caption{Схема методов целенаправленного построения тестовых программ}\label{fig:directed_methods}
\end{figure}

По соображениям эффективности целенаправленные методы генерации тестовых программ представляют б\textit{o}льшую актуальность и данная работа посвящена исследованию этого класса методов. Далее под \emph{нацеленными тестами} будут пониматься тестовые программы, построенные целенаправленным образом. Все остальные тестовые программы будут называться \emph{ненацеленными}. Если речь идет только о тестовых программах для тестовых ситуаций в определенной подсистеме микропроцессора (например, подсистеме управления памяти), то будем говорить о тестах, \emph{нацеленных на подсистему} (например, о тестах, нацеленных на подсистему управления памяти).

%Поскольку количество различных аспектов в работе микропроцессора (инструкций, их способов выполнения, особых режимов) измеряется десятками и сотнями, а кроме того из-за наличия конвейера в современных микропроцессорах в качестве ситуаций надо рассматривать не только аспекты, но и их комбинации. Поэтому количество различных ситуаций для всего микропроцессора это десятки и сотни тысяч.

%тестовые ситуации на основе ситуаций на конвейере и модели ошибок дают идею о том, что ситуации можно выражать в виде шаблонов программ....

%Целенаправленная генерация начинается с задания некоторого шаблона тестовой программы, который определяет набор инструкций, их последовательность и аргументы. В рамках целенаправленной генерации порядок инструкций и их аргументы должны быть подобраны таким образом, чтобы каждый новый тест покрывал новые, еще не покрытые тестовые ситуации. Целенаправленную генерацию можно реализовать как выполнение массовой генерации комбинаторных тестов с последующей фильтрацией, с тем чтобы оставлять только те тесты, которые дают дополнительное покрытие. Однако уже для достаточно коротких шаблонов (длиной 3-4 инструкции) перебор становится слишком большим.

%Целенаправленная генерация тестов дает по тесту на каждую ситуацию. Набор тестов, которые покрывают все ситуации, называют нацеленными тестами (нацеленными на эти ситуации). Набор ситуаций конечен, следовательно и набор нацеленных тестов конечен. Вопрос

%%(это и есть основная тема исследования)
%, как систематическим образом строить тестовые программы, чтобы в совокупности они воспроизвели все заданные <<интересные>> ситуации.


%Сложность микропроцессора определяет количество системных тестов. Если выделить различные аспекты функционирования микропроцессора (конвейер, буферы подсистемы управления памяти), то особое функционирование возникает при различных комбинациях этих аспектов. Это означает, что количество тестов должно быть не меньше произведения количества разных аспектов. Количество инструкций измеряется сотнями, а цепочек инструкций, соответственно, порядками сотен, плюс если учесть возможные аспекты в конвейере, в кэш-памяти, количество тестов получается очень большим. Для избежания проблемы такого <<взрывного>> характера количества тестов, их объединяют в классы эквивалентности --- \emph{тестовые ситуации}.

%При этом есть проблема покрытия всех потенциально интересных тестовых ситуаций. Нет никаких прямых способов создать многие из таких ситуаций нет. Например, интересно, как происходит доступ в память, когда соответствующий адрес имеется в кэш-памяти или не имеется. Или еще более тонкий анализ --- адрес имеется/или не имеется в кэш-памяти второго уровня. Среди инструкций процессора нет таких, которые были бы предназначены специально для создания таких ситуаций. Эти ситуации создаются \emph{динамически} в ходе выполнения программ.

%Микропроцессор рассматривается как черный (или серый) ящик. Входными тестовыми данными является некоторая программа, которая загружается в память. Результатом прогона теста является либо финальное состояние памяти (возможно, включая состояние регистров) или (в случае <<серого ящика>>) трасса изменения значений ячеек памяти или регистров.
%В этой общей схеме тестирования пока не упомянуты:
%\begin{itemize}
%	\item	генератор тестов (или набор уже готовых тестов);
%	\item	подсистема проверки корректности полученного результата --- тестового оракула, или арбитра;
%	\item	перечень <<интересных>> ситуаций, которые надо воспроизвести в ходе выполнения тестов;
%	\item	некая система мониторинга, которая фиксирует прохождение <<интересных>> ситуаций --- оценивает полноту покрытия.
%\end{itemize}
%
%Тестовый оракул, или арбитр, строится по схеме с использованием <<эталонной>> модели (simulation-based verification)~\cite{SimulationBased}. Каждая тестовая программа выполняется на двух моделях --- на тестируемой (design) и на <<эталонной>>. Потом состояния памяти или трассы изменения состояния памяти для тестируемой и эталонной моделей сравниваются. Если оракул признает, что трассы не эквивалентны, это свидетельствует о наличии ошибки в тестируемой системе (или эталонной, но это происходит реже). Как правило, эталонная модель пишется на одном из языков программирования (например, Си или Си++) и не загромождается деталями.  На этом основании считается, что такая модель существенно проще тестируемой, в ней с меньшей вероятностью встречаются ошибки, именно поэтому к ней можно относиться как к <<эталонной>>.
%
%% критика этого подхода: он не позволяет проверить модули, работающие за счет внешних воздействий - For example, fast interrupt request (FIQ), interrupt request (IRQ), data abort exception (Dabort) and prefetch abort exception (Pabort) of ARM7. Это пишут в статье "Automatic Verification of External Interrupt Behaviors for Microprocessor Design", авторы Fu-Ching Yang, Wen-Kai Huang, Ing-Jer Huang.
%
%
%Методы автоматической генерации тестов делят на псевдослучайные/комбинаторные (pseudo-random) и целенаправленные (что не отменяет возможности использования уже готовых тестов)~\cite{HoPhD}. В случае псевдослучайной генерации инструкции, их порядок и аргументы выбираются случайным образом или перебираются некоторым комбинаторным способом. Целенаправленная генерация начинается с задания некоторого шаблона тестовой программы, который определяет набор инструкций, их последовательность и аргументы. В рамках целенаправленной генерации порядок инструкций и их аргументы должны быть подобраны таким образом, чтобы каждый новый тест покрывал новые, еще не покрытые тестовые ситуации. Целенаправленную генерацию можно реализовать как выполнение массовой генерации комбинаторных тестов с последующей фильтрацией, с тем чтобы оставлять только те тесты, которые дают дополнительное покрытие. Однако уже для достаточно коротких шаблонов (длиной 3-4 инструкции) перебор становится слишком большим.
%
%Целенаправленная генерация тестов дает по тесту на каждую ситуацию. Набор тестов, которые покрывают все ситуации, называют нацеленными тестами (нацеленными на эти ситуации). Набор ситуаций конечен, следовательно и набор нацеленных тестов конечен. Вопрос
%%(это и есть основная тема исследования)
%, как систематическим образом строить тестовые программы, чтобы в совокупности они воспроизвели все заданные <<интересные>> ситуации.
%
%
%Перечень (конечный) <<интересных>> ситуаций и мониторинг. В совокупности две эти возможности задают метрику и механизм оценки полноты тестирования. Мониторинг организовать относительно легко, поскольку мы работаем не с реальным процессором, а с его моделями. Как построить перечень «интересных» ситуаций» --- вопрос открытый --- это одно из направлений моей работы.


\section{Тестирование подсистем управления памяти}\label{section:cache}

Подсистема управления (механизмами) памяти (MMU, Memory Management Unit) ---
логически связанный набор модулей микропроцессора, который выполняет
функции обращения к памяти~\cite{MMU}. Практически ни один
микропроцессор не обходится без подсистемы управления памяти.

Основными функциями подсистем управления памяти являются:
\begin{enumerate}
  \item \emph{трансляция адресов}: преобразование логических (виртуальных) адресов в физические;
  \item \emph{организация виртуальной памяти};
  \item \emph{организация защиты} адресного пространства процесса от других процессов;
  \item \emph{организация кэширования данных оперативной памяти} (иногда эту функцию включают в подсистемы управления памяти~\cite{vorobyev},~иногда --- нет~\cite{thompson}).
\end{enumerate}

Согласно этим функциям в число устройств, которыми управляют подсистемы управления памяти, включаются:
\begin{itemize}
  \item кэш-память (кэш-память данных и кэш-память инструкций)  первого и более высоких уровней;
  \item TLB (Translation Lookaside Buffer) -- буфер, задающий соответствие некоторых страниц виртуальной памяти кадрам физической памяти;
  \item таблица страниц -- различным образом организованное полное соответствие всех страниц виртуальной памяти кадрам физической памяти;
  \item сегментные регистры (содержат логические адреса начала сегментов);
  \item и другие буферы.
\end{itemize}

%Организация кэширования в MMU отличается от организации кэширования
%программных систем (баз данных, операционных систем) тем, что в микропроцессорах
%применяется довольно ограниченный набор стратегий вытеснения. Наиболее часто применяются
%стратегии вытеснения \LRU, \FIFO и \PseudoLRU. Это связано с особыми требованиями
%к эффективности реализации алгоритмов вытеснения в микропроцессорах (вся реализация
%алгоритма вытеснения должна располагаться на кристалле и не давать большой проигрыш по времени).

Кэш-память хранит набор блоков данных (кэш-строк). С каждым блоком данных хранится адрес в оперативной памяти этого блока данных и ряд флагов. Целью кэш-памяти является ускорение доступа к данным, хранящимся в оперативной памяти. Если во время доступа данные по нужному адресу нашлись в кэш-памяти, то используются найденные данные и обращение в оперативную память не производится. Чтобы нужные данные оказались в кэш-памяти, они должны быть туда помещены. Чтобы при этом кэш-память не увеличивалась в размерах (что чревато увеличением времени поиска данных и усложнением схемы реализации кэш-памяти), начиная с некоторого ее размера, перед добавлением новых данных из кэш-памяти удаляется один из блоков данных (этот процесс называется \emph{вытеснением}), добавление происходит на место вытесненного блока данных.

Функциональность кэш-памяти определяется в виде набора \emph{стратегий}\\ (policy):
\begin{itemize}
	\item \emph{стратегия кэширования (write policy)} (или <<политика записи>>)
		\begin{itemize}
		\item некэшируемое обращение: в этом случае кэш-память не используется;
		\item кэшируемое обращение со сквозной записью (write-through): в этом случае инструкция сохранения данных в памяти изменяет соответствующий блок данных как в кэш-памяти, так и в оперативной памяти;
		\item кэшируемое обращение с обратной записью (write-back): в этом случае инструкция сохранения данных в памяти изменяет соответствующий блок данных только в кэш-памяти, а изменение данных в оперативной памяти откладывается;
		\end{itemize}
	\item \emph{стратегия вытеснения (replacement policy)} (или <<политика замещения>>) --- правило определения вытесняемого блока данных; примеры: согласно \LRU (Least Recently Used) вытесняется блок данных, к которому не было обращений дольше, чем к остальным, согласно \FIFO (First-In First-Out) вытесняется блок данных, добавленный в кэш-память раньше остальных;
	\item \emph{стратегия чтения (read architecture)}~\cite{IntelCache}:
		\begin{itemize}
			\item сквозной доступ (look-through): в этом случае обращение сначала производится только в кэш-память и при неуспехе производится еще одно обращение --- в оперативную память или другие уровни кэш-памяти;
			\item побочный доступ (look-aside): в этом случае при обращении в кэш-память одновременно отправляются запросы во все уровни кэш-па-мяти и в оперативную память;
		\end{itemize}
	\item \emph{стратегия помещения данных}~\cite{Kasperski_EffectiveMemory} определяет, надо ли (и когда) при промахе помещать данные из оперативной памяти в кэш-память; микропроцессоры Intel Pentium и AMD всегда помещают такие данные в кэш-память;
	\item \emph{включающая/исключающая организация}:
		\begin{itemize}
		\item включающая организация (inclusive) предполагает при промахе в одном уровне кэш-памяти добавлять нужные данные и во все более быстрые уровни кэш-памяти; этой архитектуре следуют микропроцессоры AMD K6, Pentium II, Pentium III~\cite{Kasperski_EffectiveMemory};
		\item исключающая организация (exclusive) обеспечивает, что один и тот же блок данных не хранится в нескольких уровнях кэш-памяти одновременно; ей следует микропроцессор AMD Athlon~\cite{Kasperski_EffectiveMemory}.
		\end{itemize}
\end{itemize}

Типичная организация кэш-памяти следующая (см. рисунок~\ref{fig:cache_model}). Она состоит из \emph{секций}. Все секции состоят из одинакового числа \emph{кэш-строк} (line). Каждая строка содержит блок данных и \emph{тег} адреса этих данных в оперативной памяти (tag). Строки в секции проиндексированы. Строки всех секций, расположенные по одному и тому же индексу, могут хранить данные из строго определенной области памяти (в других строках данные из этой области памяти храниться не могут). Количество секций называют \emph{ассоциативностью} кэш-памяти. Получив адрес, по которому надо обратиться в кэш-память, MMU вычисляет по нему тег и индекс строк в секциях. Затем теги из строк во всех секциях по вычисленному индексу сравниваются с вычисленным тегом адреса. Если нашлась секция с тем же тегом, то выполняется нужная операция над данными из подошедшей строки. Эта ситуация называется кэш-попаданием. Если все теги в соответствующих строках секций отличны от вычисленного адреса, ситуация называется кэш-промахом. Вытесняемая строка определяется среди тех строк, по тегам которых проводилось сравнение.

\begin{figure}[h] \center
  \includegraphics[width=0.5\textwidth]{1.review/cache}\\
  \caption{Схема организации кэш-памяти}\label{fig:cache_model}
\end{figure}

По структуре выделяют следующие три типа кэш-памяти:
\begin{itemize}
   \item \emph{полностью ассоциативная} кэш-память;
   \item кэш-память \emph{прямого доступа};
   \item \emph{наборно-ассоциативная} кэш-память.
\end{itemize}
Тип определяется ассоциативностью ($W$) и количеством строк в секции ($R$). Кэш-память является полностью ассоциативной, если $R = 1$. В такой кэш-памяти поиск тега адреса осуществляется одновременно во всех строках кэш-памяти. Кэш-память является кэш-памятью прямого доступа, если $W = 1$. В такой кэш-памяти вытесняемая строка определяется однозначно (поскольку кэш-память состоит всего из одной секции). И кэш-память является наборно-ассоциативной, если $R > 1$ и $W > 1$.

%Наборно-ассоциативная кэш-память обладает лучшими показателями эффект hit ratio + ссылка! (вероятность попадания слова в кэшпамять)

Целью разработки практически любой кэш-памяти является нахождение баланса между сложностью ее схемной реализации, вероятностью промаха (miss ratio) и временем обращения. В идеальной кэш-памяти промахи не должны происходить вовсе. Предложено ряд идей для уменьшения вероятности промаха. Вот лишь некоторые из них~\cite{Kasperski_EffectiveMemory}:
\begin{itemize}
	\item увеличение числа уровней кэш-памяти;
	\item увеличение числа секций кэш-памяти;
	\item пакетный режим передачи данных --- при необходимости даже одного байта считывается вся кэш-строка целиком;
	\item конвейеризация (в том числе, конвейерно-пакетная кэш-память) --- конвейеризуются как обращения в память, так и обращения в кэш-память так, что возможно обращение в кэш-память до окончания предыдущего обращения;
	\item использование <<буферов записи>> (store buffers) --- они позволяют на некоторое время откладывать фактическую запись в кэш-память и/или оперативную память, осуществляя эту операцию по мере освобождения кэш-контроллера, внутренней или системной шины; Pentium-III содержит буфер записи из 12 строк~\cite{Kasperski_EffectiveMemory};

	%во время сквозного (write-trough) обращения сохранение данных происходит в кэш-памяти и в буфере записи (вместо оперативной памяти), затем кэш-память продолжает работать, а из буфера записи данные в своем темпе переносятся в оперативную память; тот же буфер записи используется для операций загрузки данных, что еще ускоряет выполнение загрузки;

	\item упорядочение записей к памяти --- memory order buffer расположен между конвейером и кэш-памятью; целью буфера является отслеживание обращений к памяти и их переупорядочение (например, независимые load и store можно переставлять местами); размеры буферов --- 12, 16~\cite{MOBs};
	\item программная/аппаратная предвыборка с интеллектуальным алгоритмом упреждающей загрузки в кэш-память;
	\item кэширование последних вытесненных строк (victim buffers) --- если происходят обращения к отсутствующим в кэш-памяти данным и они есть в victim buffers, то данные берутся оттуда и обращения к другим буферам (в том числе в оперативную память) не осуществляются; размер victim buffer варьируется в пределах 1-5 строк~\cite{HennesyPatterson};

%	\item псевдоассоциативность\cite{HennesyPatterson}: для кэш-промаха обращение в кэш-память осуществляется так же, как и для кэш-памяти прямого отображения; для кэш-промаха вместо обращения к другим уровням кэш-памяти осуществляется еще одно обращение в тот же уровень (например, в набор, номер которого отличается лишь инвертированием самого старшего бита).
\end{itemize}

Все эти методы неизбежно приводят к увеличению сложности алгоритмов работы кэш-памяти и становятся причиной ошибок. Методы, подобные только что перечисленным, применяются для увеличения эффективности работы и других устройств, входящих в подсистемы управления памяти.

%(отсюда будут и требования на программы и сложность состояния)

%еще есть reducing hit time! -- Hennessy Patterson (около fig.5.28)

%Увеличенный внутренний кэш (отдельный для команд и для данных) повысил производительность за счет уменьшения времени обращения к памяти и ускорения доступа к недавно использованным командам и данным.

%ускорение трансляции адреса:
%* дополнительная буферизация последних трансляций

%Каждый адрес может быть разделен на два битовых поля: поле
%\emph{тега адреса} и поле \emph{сет адреса}. Один набор составляют
%адреса с одинаковым сетом. Кэш-память организована таким образом,
%что для каждого сета хранится всегда одно и то же количество адресов
%(равное количеству секций $W$). Адреса всех данных в кэш-памяти
%различные. Отсюда следует, что теги адресов одного набора разные. В
%кэш-памяти представлены все наборы, возможные в рамках битового поля
%сета адреса.
%
%Инструкции обращения в память бывают двух видов: инструкции загрузки
%данных из памяти по данному адресу и инструкции сохранения данных в
%памяти по данному адресу. При выполнении этих инструкций может быть
%задействована кэш-память. Если данные по требуемому адресу
%присутствуют в кэш-памяти, операция проводится с нею. Такая ситуация
%называется \emph{кэш-попаданием}. Если данные по требуемому адресу
%не присутствуют в кэш-памяти, осуществляется подгрузка данных в
%кэш-память и совершение операции. Такая ситуация называется
%\emph{кэш-промахом}. В этом случае если кэш-память полностью
%заполнена, некоторые данные должны быть \emph{вытеснены} из
%кэш-памяти и на их место будут загружены данные по требуемому
%адресу. \emph{Стратегия вытеснения} (или \emph{политика замещения})
%-- это правило, по которому определяются вытесняемые данные.
%Например, могут быть вытеснены данные, которые дольше всего не были
%нужны (такая стратегия называется \LRU), или данные, которые были
%внесены в кэш-память раньше остальных (такая стратегия называется
%\FIFO).

Кроме того, ошибки возможны на каждом из этапов выполнения инструкций обращения к памяти. Вот лишь некоторые классы таких ошибок:
\begin{itemize}
  \item \emph{ошибки обработки управляющих битов}; к ошибкам этого типа относится игнорирование или неправильная интерпретация значений управляющих битов в отдельных модулях подсистемы управления памяти; например, если не зависимо от значения бита достоверности (V, Valid) TLB осуществляет преобразование виртуального адреса в физический, это является ошибкой, поскольку в случае V = 0 должно возникать исключение типа TLBInvalid; для обнаружения таких ошибок достаточно использовать по одной инструкции для каждой комбинации значений битов управляющей информации;
  \item \emph{ошибки сопоставления тегов} связаны с неправильным поиском строк в TLB и в кэш-памяти, когда, например, возвращаются данные, не соответствующие заданному адресу или когда не возвращаются никакие данные, хотя они присутствуют в буфере; поскольку в некоторых случаях на сопоставление тегов влияют значения управляющих битов, некоторые ошибки данного типа можно также отнести к первому типу (<<ошибки обработки управляющих битов>>); например, в архитектуре MIPS64 для вычисления признака попадания в TLB используется значение управляющего бита G; для обнаружения таких ошибок достаточно по одной инструкции для каждой комбинации управляющих битов (если они используются), но при этом необходимо обеспечить разные заполнения буферов;
  \item \emph{конфликты использования ресурсов} возникают при неправильном порядке доступа к ресурсам MMU при одновременном выполнении нескольких запросов к памяти; как правило, такие ошибки возникают, когда значение сигнала, используемого в одном запросе, изменяется при обработке другого запроса (в результате чего первый запрос обрабатывается некорректно); причины конфликтов обычно связаны с неправильной реализацией блокировок выполнения операций; важным частным случаем конфликтов использования ресурсов являются ошибки следующего типа: при обращении к данным кэш-памяти, которые <<только что>> были вытеснены предшествующей инструкцией, считываются <<новые>> данные, то есть данные, лежащие по другому адресу; для обнаружения ошибок, связанных с конфликтами использования ресурсов, достаточно использовать тестовые воздействия из 2-3 инструкций (две конкурирующие инструкции обращения к памяти и, если необходимо, задержка между ними);
  \item \emph{ошибки обновления/вытеснения данных} связаны с некорректным обновлением и, соответственно, вытеснением данных из буферов MMU (кэш-памяти и TLB), например, когда, вытесняются не те данные в cоответствии с используемой стратегией вытеснения (не самые старые, не самые редко используемые и т.п.) или подгружаются данные, которые уже есть в буфере; для обнаружения ошибок обновления/вытеснения данных требуются тестовые воздействия, длина которых сопоставима с ассоциативностью памяти и достигает 8-16 и более инструкций;
  \item \emph{ошибки синхронизации данных} --- это ошибки синхронизации данных между разными уровнями кэш-памяти, а также между кэш-памятью и основной памятью. Для обеспечения когерентности данных в микропроцессорах используются такие стратегии кэширования, как сквозная запись и обратная запись; выбор стратегии осуществляется с помощью управляющих битов; примером ошибки синхронизации данных является неосуществление записи <<грязных>> данных при их вытеснении из кэш-памяти в случае использования стратегии обратной записи или постоянная сквозная запись в основную память, хотя это и не требуется; для обнаружения этих ошибок достаточно использовать по одной инструкции для каждой стратегии;
  \item \emph{ошибки планирования обработки запросов}; подсистема управления памяти имеет достаточно сложную управляющую логику, в том числе касающуюся планирования обработки запросов к памяти: модули MMU могут иметь входные и выходные очереди, разные типы запросов могут иметь разные приоритеты и т.д.; ошибки рассматриваемого типа связаны с некорректной реализацией управляющей логики планирования обработки запросов; примерами ошибок являются неправильная постановка запроса в очередь, игнорирование приоритета запроса, некорректная блокировка кэш-памяти при достижении максимального числа одновременно обрабатываемых запросов; ошибки планирования обработки запросов могут приводить к исчезновению или игнорированию запросов, слишком долгой обработке запросов и другим последствиям; для обнаружения ошибок этого типа размер тестового воздействия должен быть сопоставим с максимальным числом одновременно обрабатываемых запросов, включая те, которые находятся в очередях ожидания;
  \item \emph{ошибки, вызванные исключениями} --- это ошибки обработки запросов к памяти, проявляющиеся только при возникновении исключений (от других запросов к памяти или инструкций других типов); природа таких ошибок может быть самой разной, например, это могут быть ошибки конфликтов использования ресурсов или ошибки планирования обработки запросов --- главное, что эти ошибки проявляются только при возникновении исключений; для обнаружения ошибок такого типа нужно в тестовые воздействия вставлять инструкции, вызывающие исключения.
\end{itemize}

Вывод из представленных классов ошибок такой, что для целенаправленного их выявления требуются тестовые ситуации в виде цепочек инструкций, возможно, с дополнительными ограничениями.

\section{Методы целенаправленного построения тестовых программ}

%Как было сказано ранее,     Речь идет о методах построения тестов (тестовых программ), нацеленных на достижение некоторого покрытия. Нельзя говорить о нацеленных тестах, не сказав, на покрытие чего они нацелены. Здесь есть следующие возможности (критерии покрытия):
%\begin{itemize}
%	\item покрытие по структуре функциональных требований (к разрабатываемому микропроцессору);
%	\item покрытие по структуре <<кода>> (под <<кодом>> понимается исходный текст <<синтезируемой модели>> (design'а), который готовят разработчики микропроцессора);
%	\item покрытие по модели ошибок (чаще всего под <<ошибкой>> понимается\\<<замыкание-в-0>> или <<замыкание-в-1>> какого-нибудь вентиля в схеме микропроцессора).
%\end{itemize}

В этих методах процедура построения тестовой программы работает с каждой конкретной тестовой ситуацией. Согласно схеме этих методов на рисунке~\ref{fig:directed_methods} надо ответить на следующие вопросы:
\begin{enumerate}
  \item как понимается <<тестовая ситуация>>, что является тестовой ситуацией (должен быть возможен их перебор);
  \item как происходит построение тестовой программы для заданной тестовой ситуации.
\end{enumerate}

По типу ответа на второй вопрос все методы целенаправленного построения тестовых программ делятся на два класса: методы на основе массовой генерации тестовых программ и методы непосредственного построения тестовых программ. В первом случае тестовые программы генерируются без учета тестовой ситуации до тех пор, пока не будет построена тестовая программа, в которой реализована заданная тестовая ситуация. Во втором случае тестовая ситуация (вернее, ее формализованное представление) сама становится основой генерации тестовой программы: тестовая программа строится непосредственно на основе структуры и формы тестовой ситуации.

\subsection{Методы на основе массовой генерации тестовых программ}

\begin{figure}[h] \center
  \includegraphics[width=0.5\textwidth]{1.review/methods1}\\
  \caption{Схема методов на основе массовой генерации тестовых программ}\label{fig:massive_methods}
\end{figure}

Схематично эти методы изображены на рисунке~\ref{fig:massive_methods}. В них чередуются этапы генерации тестовых программ и отбора тех, в которых осуществляются тестовые ситуации, не осуществляемые предыдущими тестовыми программами. В каждом методе определяется процедура массовой генерации тестов и процедура фильтрации. Последняя основана на выбранных тестовых ситуациях, ошибках, требованиях, частях кода модели микропроцессора.

Наиболее очевидный способ организации массового генератора --- это (псевдо)случайная генерация. Этот способ предполагает (псевдо)случайный выбор последовательности инструкций и их операндов для тестовой программы. Метод отличается невысокой трудоемкостью, но и невысокой эффективностью.

% авторы статьи, год статьи
% что тестировали ("тесты для такой-то подсистемы")
% из чего состоят тесты ("тесты состояли из .....")
% какое покрытие рассматривали ("тесты нацеливались на ...")
% каким способом генерировали тесты

Другой метод генерации --- это комбинирование кусков готовых программ. В статье Д.Вуда, Г.Гибсона и Р.Каца из Университета в Беркли 1990 года описан метод генерации тестов~\cite{Berkeley89}, который использовался для верификации реализации протокола когерентности кэшей микропроцессоров SPUR, разрабатываемых также в Беркли. Тестовыми ситуациями были различные случаи взаимодействия микропроцессоров через общую память. Авторы отметили, что явное построение тестов для каждого отдельного случая взаимодействия микропроцессоров является тяжелой задачей. Вместо этого они предложили (массово) генерировать случайным образом программы для каждого микропроцессора в отдельности, специальным образом выбирая адреса ячеек памяти в инструкциях этих программ (чтобы в кэш-памяти разных микропроцессоров оказывались одни и те же <<адреса>> данных). Разработчики модели микропроцессора пишут набор <<скриптов>>. Каждый скрипт состоит из двух программ: <<действия>> и <<проверки>>. В <<действии>> совершается некоторое тестовое воздействие (например, обращение в память одним из микропроцессоров). В <<проверке>> анализируется корректность изменения состояния микропроцессора в ответ на тестовое воздействие (например, считанное после записи значение должно совпадать с ранее записанным). Массовый генератор случайным образом выбирает <<действия>> и <<проверки>> и составляет из них тестовые программы.

%Еще две статьи по случайной генерации тестов для верификации блокировок в конвейере и арифметических алгоритмов (Maur88, Shal87 в статье Berkeley89)...............

Еще один метод массовой генерации использует генетические алгоритмы~\cite{GeneticAlgorithms}. В 2003 году исследователями из Politecnico di Torino использовали этот метод для тестирования производимых чипов микропроцессоров~\cite{microGP}. Тестовыми ситуациями были ошибки <<замыкания-в-0>> и <<замыкания-в-1>> логических вентилей схемы (в англоязычной терминологии, <<stuck-at faults>>). Это такая ситуация, когда вместо нужной функции вентиль выдает константное значение (0 или 1). Генетический алгоритм массовой генерации строит и преобразует в тексты тестовых программ ациклические ориентированный графы, в которых вершинам сопоставлены инструкции, а дуги задают поток управления тестовой программы. Хромосомами являются такие графы, генами --- вершины графа. Мутация предполагает добавление, удаление или модификацию инструкции, сопоставленной вершине. Кросс-овер понимается в виде замены подграфов. Чем больше хромосома <<обнаруживает>> замыканий вентилей, тем больше ее шанс <<выжить>>. Поэтому функция отбора выбрана такой, чтобы она линейно зависела от количества обнаруживаемых хромосомой замыканий.

\subsection{Методы непосредственного построения тестовых\\ программ}

В методах на основе массовой генерации программ тестовая ситуация использовалась лишь для отбора тестовых программ из сгенерированных массивов тестовых программ. В методах непосредственного построения тестовые программы строятся путем преобразования самой тестовой ситуации, выраженной в некоторой форме: путь в графе, слово в некотором алфавите и т.п. (см. рисунок~\ref{fig:immediate_methods}) Достаточно часто тестовые ситуации используются в форме \emph{тестовых шаблонов}.

%Тестовый шаблон состоит из последовательности инструкций, которая должна быть в тестовой программе и у каждой инструкции указан ее вариант, один из возможны способов исполнения этой инструкции. Тестовая программа соответствует тестовому шаблону тогда и только тогда, когда в ней  есть последовательность инструкций из тестового шаблона, причем каждая инструкция исполняется согласно указанным в шаблоне вариантам. Чтобы обеспечить такое соответствие, необходимо дополнить инструкции тестового шаблона инструкциями, обеспечивающими нужные для этого значения в регистрах, флагах микропроцессора, нужные данные в устройствах подсистемы управления памяти. Построение таких \emph{инициализирующих} инструкций --- основная задача генераторов тестовых программ по шаблонам.

\begin{figure}[h] \center
  \includegraphics[width=0.6\textwidth]{1.review/im_methods}\\
  \caption{Схема методов непосредственного построения тестовых программ}\label{fig:immediate_methods}
\end{figure}

Далее в этом разделе сначала будут рассмотрены методы построения тестовых шаблонов, затем методы построения тестовых программ по тестовым шаблонам и, наконец, методы построения тестовых программ, основанные на иных, нешаблонных, представлениях тестовых ситуаций.

% авторы статьи, год статьи
% что тестировали ("тесты для такой-то подсистемы")
% из чего состоят тесты ("тесты состояли из .....")
% какая модель микропроцессора используется (автоматы, графы, деревья инструкций)
% какое покрытие рассматривали ("тесты нацеливались на ...", что такое test case)
% каким способом генерировали тесты

\subsubsection{Методы построения тестовых шаблонов}%\label{sec:templates_generation_methods}

Сначала будет дан ряд определений, а затем будут описаны методы построения тестовых шаблонов.

Пусть $x_1, x_2, ..., x_n$ --- переменные с конечными множествами значений $Dx_1,$ $Dx_2, ..., Dx_n$ соответственно. Будем называть \emph{ограничением} $E$ над переменными $x_1, x_2, ..., x_n$ подмножество множества $Dx_1 \times Dx_2 \times ... \times Dx_n$ и обозначать его как $E(x_1, x_2, ..., x_n)$. Ограничение $E(x_1, x_2, ..., x_n)$ будем называть \emph{совместным}, если $E \neq \varnothing$. В противном случае будем называть ограничение \emph{несовместным}. \emph{Решением совместного ограничения} $E(x_1, x_2, ..., x_n)$ будем называть вектор $(k_1, k_2, ..., k_n)$, где $k_1 \in Dx_1, k_2 \in Dx_2, ..., k_n \in Dx_n$, такой, что $(k_1, k_2, ..., k_n) \in E$. \emph{Разрешить ограничение} --- значит найти его решение, если это ограничение совместно. Для решения задачи разрешения ограничений предложено ряд методов~\cite{CLPusingECLiPSe}.

Множество ограничений над одинаковым множеством переменных будем называть \emph{системой ограничений}. Систему ограничений $\{E_i(x_1, x_2, ..., x_n)\}_{i=1}^m$ будем называть \emph{совместной}, если $\bigcap_{i=1}^m E_i \neq \varnothing$. В противном случае систему ограничений будем называть \emph{несовместной}. \emph{Решением совместной системы ограничений} $\{E_i(x_1, x_2, ..., x_n)\}_{i=1}^m$ будем называть вектор $(k_1, k_2, ..., k_n)$, где $k_1 \in Dx_1, k_2 \in Dx_2, ..., k_n \in Dx_n$, такой, что $(k_1, k_2, ..., k_n) \in \bigcap_{i=1}^m E_i$. \emph{Разрешить систему ограничений} --- значит найти ее решение, если эта система ограничений совместна.

Пусть $\mathfrak{I} = \{I_1, I_2, ..., I_n\}$ --- множество имен \emph{инструкций}, $\mathfrak{R} = \{R_1, R_2, ...,$ $R_m\}$ --- множество имен \emph{регистров}, $\mathfrak{C} = \{C_1, C_2, ..., C_k\}$ --- множество имен \emph{констант}. Тестовая программа --- это цепочка инструкций с аргументами, программа на машинном языке. Учитывая введенные здесь символы, тестовая программа представляется последовательностью пар $(I, A)$, где $I \in \mathfrak{I}$, $A$ --- последовательность (аргументов инструкции) $a_1, a_2, ..., a_{q_I}$, где $a_i \in \mathfrak{R} \cup (\mathbb{N} \cup \{0\})$, $i = 1, 2, ..., q_I$.

Обозначим $\mathfrak{S} = \{S_1, S_2,$ ..., $S_p\}$ --- множество \emph{состояний микропроцессора} (одно состояние --- это вектор из значений, хранящихся в регистрах, и состояний подсистем микропроцессора\footnote{не будем детализировать форму представления состояния микропроцессора, дабы иметь возможность использовать разные ограничения над состояниями микропроцессора без изменения формулировок данных здесь определений}). Назовем \emph{вариантом исполнения инструкции} с аргументами $a_1, a_2, ..., a_q$, где $a_i \in \mathfrak{R} \cup \mathfrak{C}$, $i = 1, 2, ..., q$, ограничение над переменными $a_1, a_2, ..., a_q, s', s''$, где $s' \in \mathfrak{S}$ --- состояние микропроцессора перед исполнением инструкции, $s'' \in \mathfrak{S}$ --- состояние микропроцессора после исполнения инструкции.

Назовем \emph{тестовым шаблоном} последовательность троек $(I, A, E)$, где $I \in \mathfrak{I}$, $A$ --- последовательность (аргументов инструкции) $a_1, a_2, ..., a_{q_I}$, где $a_i \in \mathfrak{R} \cup \mathfrak{C}$, $i = 1, 2, ..., q_I$, $E$ --- вариант исполнения инструкции $I$. Использование одинаковых аргументов-регистров в разных инструкциях позволяет выразить зависимости по данным в тестовом шаблоне. Использование близко расположенных в тестовом шаблоне инструкций, которые помещаются на одни и те же функциональные устройства, позволяет выразить зависимости по функциональным устройствам в тестовом шаблоне.

Будем говорить, что тестовая программа $\{(I'_i, A'_i)\}_{i=1}^u$ \emph{соответствует} (или, \emph{удовлетворяет}) тестовому шаблону $\{(I''_i, A''_i, E''_i\}_{i=1}^v$, если выполнены все следующие условия:
  \begin{enumerate}
    \item $u \geqslant v$;
    \item $I''_1 = I'_{u-v+1}, I''_2 = I'_{u-v+2}, ..., I''_v = I'_u$;
    \item для каждого $i = 1, 2, ..., v$ $A'_{u-v+i}$ и $A''_i$ имеют одинаковую длину (обозначим ее $t$, $A'_{u-v+i} = \langle a'_1, a'_2, ..., a'_t \rangle$, $A''_i = \langle a''_1, a''_2, ..., a''_t \rangle$) и для каждого $j = 1, 2, ..., t$ выполнены все следующие условия:
        \begin{enumerate}
          \item $a'_j \in \mathfrak{R} \Rightarrow a''_j \in \mathfrak{R} \wedge a'_j = a''_j$;
          \item $a''_j \in \mathfrak{R} \Rightarrow a'_j \in \mathfrak{R} \wedge a'_j = a''_j$;
          \item для любого $i' = 1, 2, ..., v$ (обозначим $A'_{u-v+i'} = \langle b'_1, b'_2, ..., b'_{t'}\rangle$, $A''_{v+i'} = \langle b''_1, b''_2, ..., b''_{t'} \rangle$) если при каком-либо $j' = 1, 2, ..., t'$ $b''_{j'} = a''_j \in \mathfrak{C}$, то $b'_{j'} = a'_j \in (\mathbb{N} \cup \{0\})$;
        \end{enumerate}
    \item при любом исполнении тестовой программы (т.е. соответствующей ей последовательности состояний микропроцессора $s'_0, s'_1, ..., s'_u$) для любого $i = 1, 2, ..., v$  $(A'_i, s'_{u-v+i-1}, s'_{u-v+i}) \in E''_i$.
  \end{enumerate}

Подпрограмму $\{(I'_i, A'_i)\}_{i=1}^{u-v}$ будем называть \emph{инициализирующей подпрограммой}. Будем называть тестовый шаблон \emph{совместным}, если существует хотя бы одна тестовая программа, которая соответствует этому тестовому шаблону. В противном случае будем называть тестовый шаблон \emph{несовместным}.

Часто шаблоны тестов строятся вручную. Это позволяет достаточно точно выразить отдельные тестовые ситуации.

Ш.Ур и Й.Ядин в 1999 году предложили метод построения шаблонов тестов для верификации конвейеров на основе конечных автоматов~\cite{UrFSM}. Для определения автомата вводится набор переменных, состояние автомата представляется значениями этих переменных. Переход в автомате соответствует изменению значений переменных на очередном такте. Тестовыми ситуациями являются пути, включающие изменение выделенного подмножества переменных (изменение полного набора переменных потребовало бы слишком большого количества тестов). Каждый такой путь автоматически преобразовывается в тестовый шаблон. Вручную надо построить модель конвейера (на языке SMV) и выбрать подмножество переменных. Выбор путей будет сделан автоматически. Для компактного задания автомата в статье использован язык SMV~\cite{SMV}.

%строим модель: переменные, они изменяются на каждом такте: есть init - начальные значения, есть next - значения переменных "на следующем такте". Получается, что на каждом такте изменяется значение каждой переменной. Иными словами получается конечный автомат, состояние которого есть вектор значений переменных. Может быть очень большой, но конечный автомат. Задается он, конечно же, не матрицей смежности, а функциями, которые строят новые значения переменных по старым. Далее выбираются некоторые переменные и покрытие строится только по тем переходам в автомате, где изменяются значения этих переменных?

К.Кохно и Н.Мацумото в 2001 году предложили свой метод построения тестовых шаблонов на основе конечноавтоматной модели конвейера~\cite{mVpGen}. Состояниями автомата являются состояния конвейера (кортеж состояний отдельных стадий конвейера). Переходы между состояниями соответствуют изменению состояния конвейера на очередном такте. Переходы параметризованы инструкцией, поступающей на вход конвейера. Тестовыми ситуациями являются состояния, соответствующие конфликтам по данным, структурным конфликтам и комбинациям этих видов конфликтов. Тестовые шаблоны соответствуют путям из начального состояния в состояние, соответствующее тестовой ситуации. Пометки переходов пути из начального состояния в него дают последовательность (типов) инструкций тестового шаблона. Произвольным выбором инструкций соответствующих типов и аргументов тестовый шаблон преобразуется в тестовую программу.

А.Камкин в 2008 году предложил комбинаторный метод построения тестовых шаблонов на основе модели микропроцессора~\cite{MicroTESK}. Модель представляет собой список (классов) инструкций, в котором для каждой инструкции указаны
\begin{itemize}
\item аргументы;
\item ограничения на аргументы инструкции и состояние микропроцессора перед исполнением инструкции (в статье~\cite{MicroTESK} эти ограничения названы <<тестовыми ситуациями>>);
\item виды зависимостей по аргументам (например, две инструкции используют один и тот же регистр);
\item виды зависимостей по адресам (например, одинаковые виртуальные/физические адреса в двух инструкциях).
\end{itemize}

Тестовый шаблон представляет собой последовательность инструкций некоторой длины с выбранными для них зависимостями и <<тестовыми ситуациями>>. В работе отмечается успешное применение методики для тестирования подсистемы управления памятью и конвейеров некоторых микропроцессоров архитектуры MIPS64~\cite{mips64II}.

\subsubsection{Методы построения тестовых программ по тестовым шаблонам}%\label{sec:test_templates_generation_methods}

В литературе выделяются следующие методы построения тестовых программ по тестовым шаблонам:
\begin{enumerate}
	\item ручное написание генераторов тестовых программ~\cite{MicroTESK};
	\item псевдослучайное дополнение шаблона до тестовой программы~\cite{SEGUE1, SEGUE2, PA-RISC, TSE, Theo, mVpGen};
	\item использование генетических алгоритмов~\cite{GeneticTemplates};
	\item использование разрешения ограничений~\cite{GenesysPro, GenesysPro2004Innovations, DeepTrans, RAVEN, MAATG}.
\end{enumerate}

Довольно много работ следует методу псевдослучайного дополнения тестового шаблона до тестовой программы~\cite{SEGUE1, SEGUE2, PA-RISC, TSE, Theo, mVpGen}. В этом методе используются тестовые шаблоны, в которых варианты исполнения инструкций имеют следующий вид: $a \in \{\alpha_1, \alpha_2, ..., \alpha_n\}$, где $a$ --- один из аргументов инструкции, $\alpha_i \in (\mathbb{N} \cup \{0\})$, $i = 1, 2, ..., n$. Иными словами, тестовый шаблон представляет собой тестовую программу, в которой для переменных указано множество значений. Для получения тестового шаблона достаточно подставить для каждой такой переменной одно из значений соответствующего ей множества значений. Некоторые инструменты позволяют управлять выбором значений для переменной с помощью указания вероятностей появления определенных значений из множества значений в сгенерированном массиве тестовых программ для одного и того же тестового шаблона. Авторы статей отмечают невысокую трудоемкость таких методов построения тестовых программ и возможность тонкой настройки методов для получения отдельных специальных тестовых программ.

В статье~\cite{GeneticTemplates} предложен метод дополнения тестового шаблона до тестовой программы с использованием генетического алгоритма. Метод использовался при тестировании производимых чипов микропроцессоров. Тестовыми ситуациями были ошибки <<замыкания-в-0>> и <<замыкания-в-1>> логических вентилей микропроцессора. Рассматриваемые в этой статье тестовые шаблоны отличаются от тестовых программ лишь присутствием переменных на месте операндов инструкций. Для каждого шаблона с помощью генетического алгоритма ищутся значения операндов инструкций, при которых максимизируется количество обнаруживаемых <<замыканий>> вентилей (<<замыканий-в-1>> и <<замыканий-в-0>>). В этом генетическом алгоритме хромосомой является кортеж значений переменных, функцией отбора является количество обнаруживаемых <<замыканий>> вентилей. Авторы советуют, чтобы в тестовых шаблонах как минимум встретились все инструкции.

%! еще ATPG ? Politectico di Milano \cite{toATPG}

Другой класс статей и инструментов следует методу, основанному на разрешении ограничений ~\cite{GenesysPro, GenesysPro2004Innovations, DeepTrans, RAVEN, MAATG}. Как и прежде, тестовый шаблон содержит в себе информацию двух видов: параметрическую (шаблон --- это набор параметров, на значениях которых заданы отношения) и текстуальную (шаблон --- это будущий текст программы). В этом методе из тестового шаблона извлекается набор параметров, их множества значений и отношения на них. На этой основе строится система ограничений над значениями параметров. Разрешив выделенные для тестового шаблона ограничения, получаются значения параметров тестового шаблона. На заключительном этапе строится текст программы по вычисленным значениям параметров. Существование ряда эффективных процедур разрешения ограничений~\cite{CLPusingECLiPSe, SMT} определило эффективное использование разрешения ограничений для построения тестовых программ.

Представленные методы обладают общими чертами: во всех них из тестового шаблона выделяется набор параметров, затем (различными способами) параметры получают некоторые значения и эти значения подставляются в тестовый шаблон. Методы, основанные на разрешении ограничений, позволяют задать в шаблонах допустимое множество значений параметров более чётко. Поэтому эти методы позволяют строить тестовые программы, нацеленные на более сложные тестовые ситуации.

\subsubsection{Методы построения тестовых программ по нешаблонной форме тестовых ситуаций}%\label{sec:nontemplate_generation}

П.Мишра и Н.Дутт в 2002 году использовали инструмент model checking~\cite{ModelChecking} при генерации тестов для верификации конвейеров микропроцессоров~\cite{MishraDutt02}. Тестовые ситуации составлялись комбинацией ситуаций в отдельных стадиях конвейера и в функциональных устройствах. Генерацию тестов предлагается делать следующим образом. Вручную на языке EXPRESSION~\cite{EXPRESSION} подготовить описание архитектуры. Затем вручную (на языке SMV~\cite{SMV}) подготовить предикаты, выражающие ситуации в конвейере. После этого автоматически модель конвейера на EXPRESSION странслировать на SMV, для предикатов составить их отрицание и модель вместе с ним подать на вход инструменту SMV. Он проверяет выполнение заданного ему свойства в заданной модели. Если инструмент опровергает это свойство, то находит контрпример. Этот контрпример также автоматически транслируется в последовательность инструкций, т.е. тестовую программу. Полученная тестовая программа запускается на симуляторе (он автоматически получен по модели на EXPRESSION) с целью измерения покрытия.

П.Мишра и Н.Дутт в 2004 году модифицировали предложенный ранее метод следующим образом~\cite{MishraDutt04}. В рамках нового метода тестовые ситуации строятся в виде формул на языке инструмента SMV~\cite{SMV} на основе графовой модели конвейера, а тестовая программа строится по этой формуле с помощью инструмента SMV. Выделение тестовых ситуаций происходит следующим образом. Вручную готовится модель конвейера на языке EXPRESSION~\cite{EXPRESSION}. На ее основе строится еще одна модель конвейера - на этот раз в виде орграфа. Его вершинами являются стадии конвейера, запоминающие устройства (например, кэш-память первого уровня), инструкции и их аргументы. Дуги соответствуют отношениям использования (данных на стадиях) и порядка (стадий в рамках исполнения инструкции). Каждая вершина может быть в одном из четырех состояний (active, stalled, exception, flushed). Каждая дуга может быть в одном из трех состояний (active, stalled, flushed). Нахождение каждой вершины в одном из состояний дает тестовые ситуации. Генерация тестовой программы для заданной тестовой ситуации происходит следующим образом. Строится формула на языке SMV~\cite{SMV} о том, что вершина (или дуга) не находится в заданном состоянии. Эта формула и модель конвейера на SMV, сгенерированная по модели конвейера на EXPRESSION, подаются на вход инструменту SMV. Тот проверяет выполнение формулы на модели конвейера. Если он опровергает выполнение формулы, строит контрпример (некоторое состояние конвейера), который транслируется в тестовую программу. В последующих работах были предложены методы декомпозиции свойств и моделей и использование bounded model checking, чтобы расширить область применимости предложенного метода~\cite{Mishra09}.

П.Мишра и Н.Дутт продолжили исследования, поскольку SMV (и другие современные инструменты model checking) позволяли работать лишь с модельными примерами конвейеров. В работе~\cite{MishraDutt05} 2005 года они опубликовали метод генерации тестов для верификации конвейеров уже без использования model checking. Графовая модель конвейера осталась той же. Ее вершинами являются стадии, запоминающие устройства, инструкции и их аргументы. Дуги соответствуют отношениям использования и порядка. В статье были выделены 4 вида ошибок в конвейерах (чтение после записи в регистр дает другое значение, неверное вычисление операции, ошибки в активизации стадий конвейера, эффект <<параллельного>> исполнения инструкций) как требования на тестовые программы, на которых ошибки этих видов могут возникать. В статье описаны алгоритмы построения тестовых программ для каждого вида ошибок. Покрытие определяется на основе ситуаций в конвейере, которые определяют предложенные 4 вида ошибок. Суммируя вышесказанное, генерацию тестов предлагается делать следующим образом. Вручную готовится графовая модель конвейера и подается на вход алгоритма генерации программ для каждого вида ошибок. В этом алгоритме выделяются характерные последовательности инструкций и  дополняются до полных последовательностей инструкций (вставляются несущественные инструкции для заполнения промежутков, вычисляются нужные значения параметров и добавляются инструкции их инициализации).

В статье исследователей из Университета Карнеги-Меллон предложена методика построения тестовых программ для верификации подсистемы предсказания ветвлений~\cite{Branches99}. Методика была апробирована на микропроцессоре PowerPC 640. В этом микропроцессоре предсказание ветвлений выполняется с использованием двух кэшей. Для каждого из них авторы предлагают строить модели в виде конечных автоматов. Тестовыми ситуациями являются активизации специальных путей этих автоматов. Построение тестовой программы для выбранного пути осуществляется следующим образом. Подготавливаются программы для покрытия каждого отдельного перехода автомата. Эти программы конкатенируются согласно переходам, составляющим тестовую ситуацию. Авторы отмечают, что эта методика применима в том числе для тестирования механизмов динамического переименования регистров и блокировок в конвейере. Также они отметили, что на тестах удалось получить 100\% покрытие переходов автоматов.


\section{Анализ существующих методов целенаправленного построения  тестовых программ}

В предыдущем разделе были описаны представленные в литературе методы целенаправленной генерации тестовых программ --- в этом разделе эти методы будут проанализированы на предмет применения их для тестирования подсистем управления памяти (грубо говоря, для тестирования правильности реализации кэширования и трансляции адресов).

Анализ будет проводиться по следующим критериям:
\begin{itemize}
  \item возможность построения тестовой программы для тестовых ситуаций в работе подсистемы управления памяти (как минимум, возможность составления тестовых программ с инструкциями обращения к памяти);
  \item масштабируемость по длине программы: работает ли метод для программ из 10-15 зависимых инструкций, что дает возможность тестировать подсистему управления памяти в ситуациях, нацеленных на различные буферы, размер которых (см.раздел~\ref{section:cache}) варьируется от 4-16 строк;
  \item масштабируемость по размеру кэш-памяти;
  \item возможность нацеливания на функциональность.
\end{itemize}

Согласно этим критериям методы на основе массовой генерации тестовых программ обладают следующими характеристиками:
\begin{itemize}
  \item метод, описанный в работе \cite{Berkeley89}, имеет узкую специализацию и не подходит для тестирования подсистем управления памяти;
  \item метод, описанный в работе \cite{MishraDutt02}, не масштабируем на реальные микропроцессоры, о чем говорят и сами авторы;
  \item метод, описанный в работе \cite{microGP}, предназначен для получения тестовых программ, нацеленных на единичные замыкания схемы (stuck-at faults), его нельзя использовать напрямую для построения тестовых программ для тестирования вытеснения из кэш-памяти.
\end{itemize}

Методы непосредственного построения тестовых программ:
\begin{itemize}
  \item применение model checking~\cite{MishraDutt04} сталкивается с проблемами масштабируемости, авторам приходится придумывать нетривиальные декомпозиции, чтобы повысить допустимый размер программных моделей микропроцессоров;
  \item методы, описанные в работах~\cite{MishraDutt05, Branches99}, обладают узкой специализацией и не применимы для тестирования подсистем управления памяти;
  \item ручные методы написания генераторов тестов по шаблонам не масштабируемы по длине программы (количество зависимостей растет экспоненциально от длины шаблонов);
  \item методы псевдослучайного дополнения шаблонов не применимы для тестирования подсистем управления памяти, поскольку шаблоны включают в себя информацию о ситуациях в кэш-памяти, логика работы которой  не выражается в виде статических текстов с параметрами;
  \item применение методов, основанных на генетических алгоритмах, возможно, но надо чётко понимать, какая функция максимизируется, что неочевидно, ведь для данного шаблона надо построить всего одну тестовую программу --- произвольная тестовая программа либо соответствует шаблону, либо не соответствует, других вариантов нет; кроме того, при включении всей нужной информации в хромосому ее длина будет очень большой (в нее войдут начальное состояние микропроцессора и значения аргументов  инструкций --- их размер большой), что станет причиной плохой сходимости метода при <<глобальной>> функции отбора (включающей все гены хромосомы).
\end{itemize}

Методы, основанные на разрешении ограничений, были успешно применены для верификации реальных подсистем управления памяти (например, в PowerPC~\cite{GenesysPro}). Иными словами, они не только применимы, но и масштабируемы для реальных подсистем управления памяти.

%остаются constraints.

%метод построения шаблонов любой - все ли подходят для памяти?

Рассмотрим детальнее инструменты и методы, использующие разрешение ограничений, на предмет извлечения из них достаточных для воспроизведения описаний методов. Публикации по инструменту Genesys-Pro~\cite{GenesysPro, GenesysPro2004Innovations, GenesysSolver} оставляют достаточно много важных пробелов. Непонятно, каким образом происходит разрешение ограничений с массивами (а без таких ограничений не выразить ситуации в различных устройствах). Этот инструмент не доступен за пределами компании IBM, где он разработан. По инструменту RAVEN публикаций в открытой научной печати с описанием, допустимым для возможности воспроизведения инструмента, нет вовсе~\cite{RAVEN} --- эти подробности являются коммерческой тайной. Инструмент MAATG является академической разработкой, по нему в открытой научной печати существует единственная работа~\cite{MAATG}, однако она не описывает метод построения ограничений.

Таким образом, перспективными для построения нацеленных (на <<память>>) тестовых программ являются  методы, включающие построения отдельных тестовых шаблонов, а в качестве методов построения тестовой программы по тестовому шаблону --- разрешение ограничений. В этом классе методов нет открытых для науки методов.

%В) анализ: основываться будем на втором классе (почему он лучше? - для памяти подходит!)

%статья (1996)
%I’m Done Simulating;Now What? Verification Coverage Analysis and CorrectnessChecking of the DECchip 21164 Alpha microprocessor.
%описывает основные виды функциональной верификации:
%* assertions в RTL
%* самопроверяющиеся тесты
%* сравнение с эталоном
%
%В ней указываются методы псевдослучайно генерации тестов:
%
%W. Anderson, "Logical Verification of the NVAX CPU Chip
%Design," Digital Technical Journal, vol. 4, no. 3 (Summer 1992):
%38-46.
%-------------
%SEGUE - инженеры составляют набор шаблонов программ, которые вызывают разные события. В этих шаблонах вместо инструкций могут указываться лишь типы инструкций, вместо аргументов некий "произвольный аргумент".
%Шаблон верхнего уровня указывает, с какими вероятностями должны встречаться шаблоны нижнего уровня (которые писали для возникновения событий).
%Демоны моделируют псевдослучайное поведение среды, в которой работает микропроцессор.
%-------------
%
%4. A. Ahi, G. Burroughs, A. Gore, S. LaMar, C-Y. Lin, and A.
%Wiemann, "Design Verification of the HP 9000 Series 700 PARISC
%Workstations," Hewlett-Packard Journal (August 1992):
%34-42.
%-----
%похожее, но в HP
%-----
%
%5. D. Wood, G. Gibson, and R. Katz, "Verifying a Multiprocessor Cache Controller Using Random Test Generation," IEEE Design and Test of Computers (August 1990): 13-25.
%------------
%"модель" -- all multiprocessor interaction cases
%архитектура SPUR
%-----------
%
%тесты из одной инструкции (1982!):
%D. Bhandarkar, "Architecture Management for Ensuring Software Compatibility in the VAX Family of Computers," IEEE Computer (February 1982): 87-93.
%
%random test generation for check pipeline interlocks and arithmetic algorithms
%[TBD!] Maurer, Design Verification of the WE32106 Math Accelerator Unit
%[TBD!] Shalem Carmon, Testing the Design of the NS32532 Microprocessor
%
%S. Taylor et al. “Functional verification of a multiple-issue, out-of-order, superscalar Alpha processor - the DEC Alpha 21264 microprocessor.” In Proc. DAC, 1998, pp. 638–643.
%----
%SEGUE - но на следующем микропропессоре
%------
%
%2009:Yingpan Wu, Lixin Yu, Wei Zhuang, Jianyong Wang, "A Coverage-Driven Constraint Random-Based Functional Verification Method of Pipeline Unit," icis, pp.1049-1054, 2009 Eigth IEEE/ACIS International Conference on Computer and Information Science (icis 2009), 2009
%
%
%Mishra, Dutt:
%Generation of effective test programs for the self-test of a processor has been studied by several researchers ([2] [18] [20] [21]).
%
%Ur and Yadin [23] presented a method for generation of assembler test programs that systematically probe the micro-architecture of a PowerPC processor.
%
%Iwashita et al. [3] use a FSM based processor modeling to automatically generate test programs.
%
%================
%Alpha 21164 (21264): I’m Done Simulating;Now What? Verification Coverage Analysis and CorrectnessChecking of the DECchip 21164 Alpha microprocessor.
%NVAX: W. Anderson, "Logical Verification of the NVAX CPU Chip Design," Digital Technical Journal, vol. 4, no. 3 (Summer 1992):38-46.
%HP 9000 Series 700 PARISC:  4. A. Ahi, G. Burroughs, A. Gore, S. LaMar, C-Y. Lin, and A. Wiemann, "Design Verification of the HP 9000 Series 700 PARISC Workstations," Hewlett-Packard Journal (August 1992): 34-42.
%PowerPC, VLIW: что-то Genesys 2005
%Intel использует тесты: http://www.cs.rice.edu/~vardi/comp607/bentley.pdf


\section{Уточненная постановка задачи}\label{sec:problem_refinement}

В результате анализа существующих методов построения тестовых программ был сделан вывод о перспективности определенного класса методов построения тестовых программ (при помощи тестовых шаблонов). Поэтому уточним задачу диссертационной работы следующим образом: требуется разработать теоретически обоснованный метод автоматического построения тестовых программ, соответствующих тестовым шаблонам из инструкций обращения в память. Для такого метода должно быть проведено исследование эффективности.

%Метод должен быть описан настолько, чтобы была возможна реализация без автора.

%нужны:
%\begin{enumerate}
%  \item методы моделирования подсистемы управления памяти;
%  \item определение тестовых шаблонов и метод построения тестовых шаблонов на основе моделей подсистемы управления памяти;
%  \item метод построения тестовой программы по тестовому шаблону.
%\end{enumerate}
%
%Второй пункт подробно описан в работе~\cite{MicroTESK} и далее рассматриваться не будет. Остальные два пункта дают уточненную постановку задачи в диссертации:
%\begin{enumerate}
%  \item предложить метод моделирования подсистем управления памяти (ее решению посвящен раздел~\ref{sec:state_model_section});
%  \item предложить метод построения тестовой программы по тестовому шаблону (ее решению посвящена практически целиком следующая глава за исключением раздела~\ref{sec:state_model_section}).
%\end{enumerate}

